﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Mindless
{
    /// <summary>
    /// A list of items, designed to support a very large number of elements without putting much
    /// pressure on the garbage collector.
    /// </summary>
    class BigList<T> : IList<T>
    {
        /// <summary>
        /// The items in the list. The end of the array may be longer than necessary.
        /// </summary>
        protected BigArray<T> items;

        /// <summary>
        /// The number of items in the list. This will always be less than or equal to the length
        /// of the "items" array.
        /// </summary>
        protected int nItems;

        /// <summary>
        /// Constructs an empty list with the given capacity.
        /// </summary>
        public BigList(int capacity)
        {
            this.items = this.AllocateItems(capacity);
            this.nItems = 0;
        }

        /// <summary>
        /// Constructs an empty list.
        /// </summary>
        public BigList() : this(16)
        {
        }

        /// <summary>
        /// Allows a base class to allocate its own subtype of array.
        /// </summary>
        protected virtual BigArray<T> AllocateItems(int nItems)
        {
            return new BigArray<T>(nItems);
        }

        /// <summary>
        /// The receiver's capacity. This is the number of items it can hold without having to grow
        /// (i.e. acquire more memory). Attempts to set this to a value that is less than the receiver's
        /// current capacity will have no effect.
        /// </summary>
        public int Capacity
        {
            get { return this.items.Length; }
            set
            {
                if (value > this.items.Length)
                {
                    BigArray<T> ts = this.AllocateItems(value);
                    this.items.CopyTo(ts, this.nItems, 0);
                    this.items = ts;
                }
            }
        }

        /// <summary>
        /// Increases the capacity of the receiver to at least the given amount.
        /// </summary>
        void Grow(int min)
        {
            this.Capacity = Math.Max(2 * this.items.Length, min);
        }

        /// <summary>
        /// Attempts to decrease the capacity of the receiver so that it is equal to the number of items
        /// in the receiver. If this cannot be accomplished (e.g. due to out-of-memory), the receiver is
        /// unaffected.
        /// </summary>
        public void TrimExcess()
        {
            try
            {
                BigArray<T> ts = this.AllocateItems(this.nItems);
                this.items.CopyTo(ts, this.nItems, 0);
                this.items = ts;
            }
            catch (OutOfMemoryException)   // out of memory should not be fatal in this situation
            {
            }
        }

        /// <summary>
        /// Sorts the receiver using the given comparison.
        /// </summary>
        public void Sort(Comparison<T> comparison)
        {
            this.items.Sort(0, this.nItems - 1, comparison);
        }

        /// <summary>
        /// Answers the index of the given item within the receiver, or -1 if not found.
        /// </summary>
        public int IndexOf(T item)
        {
            int index = this.items.IndexOf(item);

            return (index >= this.nItems) ? -1 : index;
        }

        public void Insert(int index, T item)
        {
            throw new NotImplementedException();
        }

        public void RemoveAt(int index)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Accesses the item at the given index within the receiver.
        /// </summary>
        public T this[int index]
        {
            get
            {
                if (index >= this.nItems)
                    throw new ArgumentOutOfRangeException();

                return this.items[index];
            }
            set
            {
                if (index >= this.nItems)
                    throw new ArgumentOutOfRangeException();

                this.items[index] = value;
            }
        }

        /// <summary>
        /// Adds the given item at the end of the receiver, growing the receiver's capacity
        /// if necessary.
        /// </summary>
        public void Add(T item)
        {
                // make sure we have room for the new item
            if (this.nItems == this.items.Length)
                this.Grow(this.nItems + 1);

            this.items[this.nItems++] = item;
        }

        /// <summary>
        /// Empties the receiver.
        /// </summary>
        public void Clear()
        {
            this.items.Initialize();   // release items so they can be GC'ed
            this.nItems = 0;
        }

        /// <summary>
        /// Indicates whether the receiver contains the given item.
        /// </summary>
        public bool Contains(T item)
        {
            return this.IndexOf(item) != -1;
        }

        /// <summary>
        /// Copies the receiver's items to the given array starting at the given index.
        /// </summary>
        public void CopyTo(T[] array, int arrayIndex)
        {
            foreach (T t in this)
                array[arrayIndex++] = t;
        }

        /// <summary>
        /// Answers the number of items in the receiver.
        /// </summary>
        public int Count
        {
            get { return this.nItems; }
        }

        /// <summary>
        /// Indicates whether the receiver is read-only.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Removes the given item from the receiver, if it exists.
        /// </summary>
        public bool Remove(T item)
        {
            int index = this.IndexOf(item);
            if (index != -1)
                this.RemoveAt(index);

            return index != -1;
        }

        /// <summary>
        /// Enumerates the receiver's items.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < this.nItems; ++i)
                yield return this.items[i];
        }

        /// <summary>
        /// Enumerates the receiver's items.
        /// </summary>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}
